#include <iostream>
#include <queue>

using namespace std;

/* Program description:
   Breadth first search for a graph
  
  Algorithm design
   Using adjacency matrix to store the graph
   Using queue to store the nodes being visited
   From the queue,
     dequeue the node
     if the neighbor of the nodes have not been visited, enqueue the neighbor
   until queue is empty (or the nodes have all been visited)
*/

#define MAX 5
#define NOTVISITED	0		// the item is not visited yet
#define VISITING	1		// Indicate the item is in the queue but not print yet (to avoid double insert)
#define VISITED		2		// The item has been visted and printed

void i_bfs(int adj[MAX][MAX], int *visited, int start)
{
	queue<int> Queue;

	if( visited[start] != NOTVISITED )
		return;

	Queue.push(start);	
	visited[start] = VISITING;
	while(!Queue.empty())
	{
		int cur = Queue.front();
		Queue.pop();
		visited[cur] = VISITED;
		cout<<"Visit node "<<cur<<endl;
		for(int j=1;j<=MAX;j++)
        {
			if(adj[start][j]!=0 && visited[j]==NOTVISITED)
			{
				visited[j]=VISITING;
				Queue.push(j);
			}
        }
	}
    return;
}

void BFS( int adj[MAX][MAX] )
{
	int visited[MAX] = {NOTVISITED};

	for( int i=0; i<MAX; i++ )
	{
		if(visited[i] != NOTVISITED )
			continue;
		i_bfs( adj, visited, i );
	}
}

int main()
{
    int adj[MAX][MAX]={{0,0,1,1,0},{0,0,0,0,0},{0,1,0,0,1},{0,0,0,0,1},{0,0,0,1,0}};
    BFS(adj);

	cout<<"Press any key to terminate..."<<endl;
	return getchar();
}
